#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

struct ListNode
{
    int val;
    struct ListNode* next;
};

ListNode* createNewNode(int val)
{
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode)
    {
        newNode->val = val;
        newNode->next = NULL;
    }
    return newNode;
}

void destroyNode(ListNode* head)
{
    ListNode* current = head;
    while (current)
    {
        ListNode* temp = current;
        current = current->next;
        free(temp);
    }
}

void printNode(ListNode* head)
{
    ListNode* current = head;
    cout << "结点的数据为： ";
    while (current)
    {
        cout << current->val << " ";
        current = current->next;
    }
    cout << "\n";
}

ListNode* constructList(int listSize)
{
    ListNode* head = NULL;
    ListNode* current = NULL;

    srand(time(0));

    for (int i = 0; i < listSize; ++i)
    {
        int randomVal = rand() % 100;
        ListNode* newNode = createNewNode(randomVal);
        if (!newNode)
        {
            // 内存分配失败
            destroyNode(head);
            return NULL;
        }
        if (!head)
        {
            head = newNode;
            current = head;
        }
        else
        {
            current->next = newNode;
            current = newNode;
        }
    }

    return head;
}

ListNode* sortNodeData(ListNode* head)
{
    if (!head || head->next == NULL)
        return head;

    ListNode* sort = NULL;
    ListNode* current = head;

    while (current)
    {
        ListNode* nextNode = current->next;
        if (!sort || sort->val >= current->val)
        {
            current->next = sort;
            sort = current;
        }
        else
        {
            ListNode* temp = sort;
            while (temp->next && temp->next->val < current->val)
            {
                temp = temp->next;
            }
            current->next = temp->next;
            temp->next = current;
        }
        current = nextNode;
    }
    head = sort;
    return head;
}

int main()
{
    int listSize = 5;
    ListNode* head = constructList(listSize);
    if (!head)
    {
        cout << "创建失败： \n";
        return 1;
    }
    cout << "未排序前： " << endl;
    printNode(head);
    cout << "排序后： " << endl;
    head = sortNodeData(head);
    printNode(head);

    return 0;
}
